#include <iostream>
#include <ostream>
#include <vector>
#define lld long long // long long 的 printf 占位符是 lld
#define ENDL '\n'     // 将 endl 替换为 \n 取消缓冲区
#define mod %
#define LOG(var) std::cout << #var << " = " << (var) << ENDL
const lld N = 1e5 + 9;
const lld MOD_N = 1e9 + 7;
const lld MAX_ = 1e9;

using std::cin;
using std::cout;
using std::string;
using std::vector;

const lld MOD = 1e9 + 7;

struct Matrix {
  vector<vector<lld>> mat;
  int r, c;
  Matrix(int _r, int _c) : r(_r), c(_c) { mat.resize(r, vector<lld>(c, 0)); }

  Matrix operator*(Matrix &b) {
    Matrix res(r, b.c);
    for (int i = 0; i < r; ++i)
      for (int k = 0; k < c; ++k)
        for (int j = 0; j < b.c; ++j)
          res.mat[i][j] = (res.mat[i][j] + mat[i][k] * b.mat[k][j]) % MOD;
    return res;
  }
};

Matrix pow(Matrix a, lld n) {
  Matrix res(a.r, a.c);
  for (int i = 0; i < res.r; ++i)
    res.mat[i][i] = 1;
  while (n > 0) {
    if (n & 1)
      res = res * a;
    a = a * a;
    n >>= 1;
  }
  return res;
}

lld solve(int n) {
  if (n == 0)
    return 1;
  if (n == 1)
    return 2;
  if (n == 2)
    return 5;

  
  vector<lld> base = {5, 2, 1};

  
  Matrix M(3, 3);
  M.mat = {{2, 0, 1}, {1, 0, 0}, {0, 1, 0}};

  Matrix Mp = pow(M, n - 2);

  
  lld res = 0;
  for (int i = 0; i < 3; ++i) {
    res = (res + Mp.mat[0][i] * base[i]) % MOD;
  }

  return res;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    cout << solve(n) << "\n";
  }
  return 0;
}